The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Network devices, such as network switches, routers, edge devices and the like, perform exact-match lookups in database using keys that are derived from information associated with received packets received. Some such databases are implemented as hash tables. In such systems, a hash function is applied to a key to generate a hash value corresponding to the key, and the hash value is used to access the database in an attempt to locate the key in the database. If a match is found, information associated with the key, such as information indicative of a processing operation or an action to be performed on the packet, is retrieved from the database, and the information is used to further process the packet. However, such hash tables exhibit inherent collisions when a hash function generates a same hash value for two or more different keys provided to the hash function, and as a result, some keys provided to a hash table cannot be inserted into the hash table. As a result, some entries cannot be inserted into the hash table, resulting in loss of keys and, in at least some cases, low utilization of the hash table.